1467D - Sum of Paths - CodeForces Solution

               //  ॐ
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ld long double
typedef pair<int,int>       pii;
typedef pair<ll,ll>       pll;
typedef vector<ll> vll;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<ll>>;
#define pb              push_back 
#define Sort(a)         sort(a.begin(),a.end())
#define ff                  first
#define ss                  second 
const int N = 1e3 + 5;
const ll f = 1e9 + 7;

void solve(){
    int n,k,q;
    cin>>n>>k>>q;

    vvll dp1(k+1,vll(n+2,0));
    for (int i = 1; i <= n; ++i)
        dp1[0][i]=1;

    for (int j = 1; j <= k; ++j){
        for (int i = 1; i <= n; ++i){
            dp1[j][i] = (dp1[j-1][i-1] + dp1[j-1][i+1])%f;
        }
    }

    vvll dp(k+1,vll(n+2,0));
    for (int j = 0; j <= k; ++j){
        for (int i = 1; i <= n; ++i){
            dp[j][i] = (dp1[j][i] * dp1[k-j][i])%f;
        }
    }

    vll sum(n+1,0); 
    for (int i = 1; i <= n; ++i){
        for (int j = 0; j <= k; ++j){
            sum[i] += dp[j][i]; sum[i]%=f;
        }
    }

    vll ar(n+1,0); ll ans = 0;
    for (int i = 1; i <= n; ++i){
        cin>>ar[i];
        ans += (sum[i]*ar[i])%f;
        ans %= f;
    }

    while(q--){
        int i, x;
        cin>>i>>x;
        ans += f - (sum[i]*ar[i])%f;
        ans %= f; ar[i] = x;
        ans += (sum[i]*ar[i])%f;
        ans %= f;
        cout<<ans<<"\n";
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t=1;
    // cin>>t;
    while(t--)
        solve();
 
}